/*
 * Copyright (c) 2004-2005 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *
 * Date:    Mar. 2011
 */

#include "base/intmath.hh"
#include "base/trace.hh"
#include "base/bitfield.hh"
#include "cpu/edge/pred/ibtb_tonb.hh"

IBTB::IBTB(unsigned _numEntries, unsigned _blockShiftAmt, std::string index_type)
    :numEntries(_numEntries),
     blockShiftAmt(_blockShiftAmt),
     indexType(Unknown)
{
    DPRINTF(EdgePredUnit, "IBTB: Creating IBTB objects.\n");
    DPRINTF(EdgePredUnit, "IBTB: Setting index type to %s.\n",
            index_type.c_str());

    if (!isPowerOf2(numEntries)) {
        fatal("IBTB entries is not a power of 2!");
    }

    ibtb.resize(numEntries);

    for (unsigned i = 0 ; i < numEntries ; ++i) {
        ibtb[i].target = 0;
        ibtb[i].hysteresis = false;
        ibtb[i].valid = false;
    }

    idxMask = numEntries - 1;

    idxLength = floorLog2(numEntries);

    if (index_type == "GlobalHistory") {
        indexType = GlobalHistory;
    } else if (index_type == "PathHistory") {
        indexType = PathHistory;
    } else if (index_type == "ConPathHistory") {
        indexType = ConPathHistory;
    } else if (index_type == "HybridHistory") {
        indexType = HybridHistory;
    } else {
        fatal("Unrecognized index type of ibtb selected.\n");
    }
}

void
IBTB::reset() 
{
    for(unsigned i = 0 ; i < numEntries ; ++i) {
        ibtb[i].target = 0;
        ibtb[i].hysteresis = false;
        ibtb[i].valid = false;
    }
}

uint64_t
IBTB::calcIndex(const Addr &PC, uint64_t hist, uint64_t path_hist)
{
    if (indexType == GlobalHistory) {

        return ((PC >> blockShiftAmt) ^ hist) & idxMask;

    } else if (indexType == PathHistory) {

        return ((PC >> blockShiftAmt) ^ path_hist) & idxMask;

    } else if (indexType == ConPathHistory) {

        uint64_t pattern = bits(path_hist, 8, 0);

//        for (int i = 1; i < 16; i++) {
//            pattern ^= bits(path_hist, (i + 1) * 4, i * 4);
//        }

        uint64_t concatenate = ((PC >> blockShiftAmt) << 8) | (pattern & 0xFF); 

        return concatenate & idxMask;

    } else if (indexType == HybridHistory) {

        return ((PC >> blockShiftAmt) ^ hist ^ path_hist) & idxMask;

    } else {

        assert(0 && "Unrecognized index type of ibtb selected.\n");
        return 0;

    }
}

Addr
IBTB::lookup(const Addr &PC, uint64_t hist, uint64_t path_hist) 
{
    uint64_t ibtb_idx = calcIndex(PC, hist, path_hist);

    DPRINTF(EdgePredUnit, "Lookup the indirect btb,"
            " get target: %#x\n",
            ibtb[ibtb_idx].target);

    // If this entry is not valid, return the PC itself.
    if (!(ibtb[ibtb_idx].valid)) {
        return PC;
    }

    Addr target = (ibtb[ibtb_idx].target) << blockShiftAmt;

    return target;
}

void
IBTB::update(const Addr &PC, uint64_t hist, uint64_t path_hist, Addr corr_target) 
{
    //update ibtb table.
    unsigned ibtb_idx =calcIndex(PC, hist, path_hist);
    IBTBEntry ibtbEntry = ibtb[ibtb_idx];
    IBTBEntry new_ibtbEntry;
    Addr target = (corr_target >> blockShiftAmt);
    new_ibtbEntry.target = ibtbEntry.hysteresis ? ibtbEntry.target : target;
    new_ibtbEntry.hysteresis = (ibtbEntry.target == target);
    ibtb[ibtb_idx] = new_ibtbEntry;

    ibtb[ibtb_idx].valid = true;

    DPRINTF(EdgePredUnit,"Block [PC=%#x, hist=%#x]"
            " BTB updated(old target = %#x, target = %#x).\n",
            PC,
            hist,
            ibtbEntry.target,
            new_ibtbEntry.target);
}

